package com.company.Graph.Dijkstra;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}9:29
 */
public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A','B','C','D','E','F','G'};
        int N = 66666;
        // 邻接矩阵
        int[][] matrix = {
                {N,5,7,N,N,N,2},
                {5,N,N,9,N,N,3},
                {7,N,N,N,8,N,N},
                {N,9,N,N,N,4,N},
                {N,N,8,N,N,5,4},
                {N,N,N,4,5,N,6},
                {2,3,N,N,4,6,N}
        };
        Graph graph = new Graph(vertex,matrix);
        graph.showGraph();
        graph.dsj(6);
        graph.showdsj();
    }
}

class Graph{
    private char[] vertex; // 顶点数组
    private int[][] matrix; // 邻接矩阵
    private VisitedVertex vv;// 已经访问顶点的集合
    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    // 显示图
    public void showGraph(){
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public void dsj(int index){
        vv = new VisitedVertex(vertex.length,index);
        update(index);// 更新index顶点到周围顶点的距离和前驱结点

        for (int j = 1; j < vertex.length; j++){
            index = vv.updateArr();// 选择并返回新的访问顶点
            update(index);// 更新index顶点到周围顶点的距离和前驱顶点
        }
    }

    // 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
    public void update(int index){
        int len = 0;
        // 根据遍历我们的邻接矩阵的 matrix[index]行
        for (int j = 0; j < matrix[index].length; j++){
            // len 含义是：出发顶点到index顶点的距离 + 从index顶点到j顶点的距离和
            len = vv.getDis(index) + matrix[index][j];

            // 如果j这个顶点没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
            if (!vv.in(j) && len < vv.getDis(j)){
                vv.update_pre(j,index);
                vv.updateDis(j,len);
            }
        }
    }

    public void showdsj(){
        vv.show();
    }


}

class VisitedVertex{// 已访问的节点集合
    public int[] already_arr;
    // 记录各个顶点是否访问过 1表示访问过 0表示未访问 会动态更新

    public int[] pre_vistied;
    // 每个下标对应的值为前一个顶点下标，会动态更新

    public int[] dis;
    // 记录出发顶点到其他所有顶点的距离，比如G为出发点，就会记录G到其他顶点的距离，会动态更新，求的最短距离就会存放到dis


    /**
     *
     * @param length 表示顶点的个数
     * @param index 出发顶点
     */
    public VisitedVertex(int length,int index) {
        this.already_arr = new int[length];
        this.dis = new int[length];
        this.pre_vistied = new int[length];
        // 初始化dis数组
        Arrays.fill(dis,Integer.MAX_VALUE);
        this.dis[index] = 0;// 设置出发顶点的访问距离为0
        this.already_arr[index] = 1;// 设置出发顶点访问为1

    }

    /**
     * 判断index顶点是否被访问过
     * @param index
     * @return
     */
    public boolean in(int index){
        return already_arr[index] == 1;
    }

    /**
     * 更新出发顶点到index顶点的距离
     * @param index
     * @param len
     */
    public void updateDis(int index,int len){
        dis[index] = len;
    }

    /**
     * 更新pre这个顶点的前驱为index的结点
     * @param pre
     * @param index
     */
    public void update_pre(int pre,int index){
        pre_vistied[index] = pre;
     }

    /**
     * 返回出发点对index顶点的距离
     * @param index
     * @return
     */
    public int getDis(int index){
        return dis[index];
    }

    /**
     * 继续选择并返回新的访问顶点，比如这里的G访问完后，就是A作为新的访问顶点（注意不是出发顶点）
     * @return
     */
    public int updateArr(){
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < already_arr.length; i++){
            if (already_arr[i] == 0 && dis[i] < min){
                min = dis[i];
                index = i;
            }
        }
        // 更新index顶点被访问过
        already_arr[index] = 1;
        return index;
    }

    // 显示最后的结果
    public void show(){
        System.out.println("===========================");
        for (int i : already_arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        // 输出前驱节点
        for (int i : pre_vistied) {
            System.out.print(i + " ");
        }
        System.out.println();
        // 输出dis数组
        for (int di : dis) {
            System.out.print(di + " ");
        }
        System.out.println();

        // 为了好看处理一下
        char[] vertex = {'A','B','C','D','E','F','G'};
        int count = 0;
        for (int i : dis){
            if (i != 66666){
                System.out.print(vertex[count] + "("+ i +")");
            }else {
                System.out.println("N");
            }
            count++;
        }
        System.out.println();
    }
}